package com.uraurora.crescent.util;

import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.graph.ElementOrder;
import com.google.common.graph.MutableValueGraph;
import com.google.common.graph.ValueGraph;
import com.google.common.graph.ValueGraphBuilder;
import com.uraurora.crescent.tuple.Tuple2;

import java.util.*;

import static com.uraurora.crescent.util.Distributions.*;

/**
 * @author : gaoxiaodong04
 * @program : crescent
 * @date : 2020-10-09 20:36
 * @description :
 */
public abstract class Graphs {

    private static class ValueNode<N, V>{
        private final N node;

        private final V value;

        public ValueNode(N node, V value) {
            this.node = node;
            this.value = value;
        }

        public N getNode() {
            return node;
        }

        public V getValue() {
            return value;
        }

        @Override
        public String toString() {
            return "ValueNode{" +
                    "node=" + node +
                    ", value=" + value +
                    '}';
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            ValueNode<?, ?> valueNode = (ValueNode<?, ?>) o;
            return Objects.equals(node, valueNode.node) &&
                    Objects.equals(value, valueNode.value);
        }

        @Override
        public int hashCode() {
            return Objects.hash(node, value);
        }
    }

    /**
     * dijkstra算法，计算有向无环图的最短路径
     * @param graph 有向无环图，且边有权重
     * @param start 起始点
     * @param end 终点
     * @param distribution 描述权重计算的接口
     * @param <N> 点的类型
     * @param <V> 权重类型
     * @return 返回一个包含最小权重和起点到终点路径的二元组
     */
    public static <N, V extends Comparable<? super V>> Tuple2<V, List<N>> dijkstra(ValueGraph<N, V> graph, N start, N end, Distribution<V> distribution){
        List<N> path = Lists.newArrayList(end);

        Map<N, V> distance = Maps.newHashMap();
        Map<N, N> paths = Maps.newHashMap();
        graph.nodes().forEach(n-> distance.put(n, distribution.maxValue()));
        distance.put(start, distribution.minValue());

        PriorityQueue<ValueNode<N, V>> queue = new PriorityQueue<>(Comparator.comparing(ValueNode::getValue));
        queue.add(new ValueNode<>(start, distribution.minValue()));

        ValueNode<N, V> currentValueNode;
        N currentNode;

        while(!queue.isEmpty()){
            currentValueNode = queue.poll();
            currentNode = currentValueNode.node;
            if(distance.get(currentNode).compareTo(currentValueNode.value) >= 0){
                for(N node : graph.successors(currentNode)){
                    final V val = graph.edgeValue(currentNode, node).orElse(distribution.defaultValue());
                    if(distance.containsKey(currentNode) && distance.containsKey(node)){
                        final V dist1 = distance.get(currentNode), dist2 = distance.get(node);
                        final V sum = distribution.plus(dist1, val);
                        if(sum.compareTo(dist2) < 0){
                            distance.put(node, sum);
                            paths.put(node, currentNode);
                            queue.add(new ValueNode<>(node, sum));
                        }
                    }
                }
            }
        }
        currentNode = end;
        while(!currentNode.equals(start)){
            currentNode = paths.get(currentNode);
            path.add(currentNode);
        }
        Collections.reverse(path);
        return Tuple2.of(distance.get(end), path);
    }

    public static void main(String[] args) {
        MutableValueGraph<String, Integer> graph = ValueGraphBuilder.directed()
                .nodeOrder(ElementOrder.insertion())
                .expectedNodeCount(10)
                .build();


        graph.putEdgeValue("A", "B", 5);
        graph.putEdgeValue("A", "C", 1);
        graph.putEdgeValue("B", "D", 1);
        graph.putEdgeValue("C", "B", 2);
        graph.putEdgeValue("C", "D", 4);
        graph.putEdgeValue("C", "E", 8);
        graph.putEdgeValue("D", "F", 6);
        graph.putEdgeValue("E", "D", 3);

        final Tuple2<Integer, List<String>> objects = dijkstra(graph, "A", "F", new IntegerDistribution());
        System.out.println(objects.get(0));
        System.out.println(objects.get(1));
    }

}
